Grokking Oracle Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Oracle Easy
Count Number of Pairs With Absolute Difference K (easy)
Solution: Count Number of Pairs With Absolute Difference K
Degree of an Array (easy)
Solution: Degree of an Array
Find Subsequence of Length K With the Largest Sum (easy)
Solution: Find Subsequence of Length K With the Largest Sum
Rectangle Overlap (easy)
Solution: Rectangle Overlap
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Island Perimeter (easy)
Solution: Island Perimeter
Climbing Stairs (easy)
Solution: Climbing Stairs
Move Zeroes (easy)
Solution: Move Zeroes
Excel Sheet Column Title (easy)
Solution: Excel Sheet Column Title
Valid Parentheses (Easy)
Solution: Valid Parentheses
Longest Palindromic Substring (medium)
Solution: Longest Palindromic Substring
Single Element in a Sorted Array (medium)
Solution: Single Element in a Sorted Array
Pairs of Songs With Total Durations Divisible by 60 (medium)
Solution: Pairs of Songs With Total Durations Divisible by 60
Search a 2D Matrix II (medium)
Solution: Search a 2D Matrix II
Minimize Maximum of Array (medium)
Solution: Minimize Maximum of Array
Asteroid Collision (medium)
Solution: Asteroid Collision
Combination Sum (medium)
Solution: Combination Sum
Binary Tree Right Side View (medium)
Solution: Binary Tree Right Side View
Sort Colors (medium)
Solution: Sort Colors
Group Anagrams (Medium)
Solution: Group Anagrams
Decode String (Medium)
Solution: Decode String
Number of Islands (medium)
Solution: Number of Islands
Binary Tree Zigzag Level Order Traversal (medium)
Solution: Binary Tree Zigzag Level Order Traversal
Longest Common Subsequence (medium)
Solution: Longest Common Subsequence
Rotting Oranges (medium)
Solution: Rotting Oranges
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Delete Node in a BST (medium)
Solution: Delete Node in a BST
Remove Duplicate Letters (medium)
Solution: Remove Duplicate Letters
Longest Substring Without Repeating Characters (medium)
Solution: Longest Substring Without Repeating Characters (medium)
Search in Rotated Array (medium)
Solution: Search in Rotated Array
Spiral Matrix (medium)
Solution: Spiral Matrix
Container With Most Water (Medium)
Solution: Container With Most Water
3Sum (medium)
Solution: 3Sum
Simplify Path (medium)
Solution: Simplify Path
Next Permutation (medium)
Solution: Next Permutation
Basic Calculator II (medium)
Solution: Basic Calculator II
Merge Intervals (medium)
Solution: Merge Intervals
Restore IP Addresses (medium)
Solution: Restore IP Addresses
Longest Increasing Subsequence (medium)
Solution: Longest Increasing Subsequence
Validate Binary Search Tree (medium)
Solution: Validate Binary Search Tree
Integer to English Words (hard)
Solution: Integer to English Words
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Merge K Sorted Lists (hard)
Solution: Merge K Sorted Lists
Max Points on a Line (hard)
Solution: Max Points on a Line
Sudoku Solver (hard)
Solution: Sudoku Solver
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Remove Nth Node From End of List (Medium)
Solution: Remove Nth Node From End of List
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Constrained Subsequence Sum (hard)
Solution: Constrained Subsequence Sum
Solution: Move Zeroes

Problem Statement

Given an array of integers nums, move all the 0s present in the array to the end while maintaining the relative order of the non-zero elements.

Note: This rearrangement should be done in-place without using extra space for another array.

Example 1:

  • Input: [1, 0, 2, 0, 3, 0, 4]
  • Expected Output: [1, 2, 3, 4, 0, 0, 0]
  • Justification: Here, all non-zero elements (1, 2, 3, 4) retain their order, and all zeros are moved to the end of the array.

Example 2:

  • Input: [0, 0, 0, 10, 20]
  • Expected Output: [10, 20, 0, 0, 0]
  • Justification: The non-zero elements (10, 20) are shifted to the front, and the zeros are relocated to the end.

Example 3:

  • Input: [5, 1, 0, 2, 0]
  • Expected Output: [5, 1, 2, 0, 0]
  • Justification: Non-zero elements (5, 1, 2) maintain their sequence, while zeros are moved to the end.

Solution

To solve this problem, we will use a two-pointer approach. The first pointer (i) will iterate over the array, and the second pointer (lastNonZeroIndex) will keep track of the position where the next non-zero element should be placed.

This approach is efficient as it allows us to perform the operation in-place, reducing the space complexity. It's also effective because it ensures that the relative order of non-zero elements is maintained by sequentially filling non-zero elements from the start. As we iterate through the array, we swap non-zero elements with the element at the lastNonZeroIndex and increment lastNonZeroIndex. This method is optimal as it requires a single pass over the array, ensuring linear time complexity.

Step-by-step algorithm

  • Initialize lastNonZeroIndex to 0.
  • Iterate through each element (i) in the array:
    • If the current element is not zero:
      • Swap the element at i with the element at lastNonZeroIndex.
      • Increment lastNonZeroIndex.
  • This process groups all non-zero elements at the beginning of the array and zeros at the end, maintaining their original order.

Algorithm Walkthrough

Let's take Example 1 [1, 0, 2, 0, 3, 0, 4]:

  • Start with lastNonZeroIndex = 0 and i = 0.
  • Iterate through the array:
    • At i = 0, element 1 is non-zero, swap it with itself, and increment lastNonZeroIndex to 1.
    • At i = 1, element 0 is zero, continue.
    • At i = 2, element 2 is non-zero, swap it with the first 0 (at index lastNonZeroIndex, which is 1), lastNonZeroIndex becomes 2.
    • At i = 3, element 0 is zero, continue.
    • At i = 4, element 3 is non-zero, swap it with the 0 (at index lastNonZeroIndex, which is 2), lastNonZeroIndex becomes 3.
    • At i = 5, element 0 is zero, continue.
    • At i = 6, element 4 is non-zero, swap it with the 0 (at index lastNonZeroIndex, which is 3), lastNonZeroIndex becomes 4.
  • Resulting array after completion: [1, 2, 3, 4, 0, 0, 0].

Code

Java

. . . .

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the array, as We iterate through the array once.
  • Space Complexity: O(1), as the rearrangement is done in-place without using extra space.
Move Zeroes (easy)
Excel Sheet Column Title (easy)
Mark as Completed

On this page

Problem Statement

Example 1:

Example 2:

Example 3:

Solution

Step-by-step algorithm

Algorithm Walkthrough

Code

Complexity Analysis